package com.ibm.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

import com.ibm.util.exception.CPSException;

public class TopologySort {

	public static List<String> sortTopology(
			Map<String, Collection<String>> parent2Successors)
			throws CPSException {
		List<String> sortedList = new ArrayList<String>();
		if (parent2Successors == null || parent2Successors.size() < 1) {
			return sortedList;
		}

		Map<String, Integer> id2Indegree = calculateIndegree(parent2Successors);
		Stack<String> zeroIndegreePoint = new Stack<String>();

		for (Map.Entry<String, Integer> entry : id2Indegree.entrySet()) {
			if (entry.getValue() == 0) {
				zeroIndegreePoint.push(entry.getKey());
			}
		}

		if (zeroIndegreePoint.size() == 0) {
			throw new CPSException(ErrorCode.INVALID_INPUT_ERROR,
					"This is a cyclic input.");
		}

		String currentPoint;
		while (!zeroIndegreePoint.isEmpty()) {
			currentPoint = zeroIndegreePoint.pop();
			sortedList.add(currentPoint);
			if (parent2Successors.get(currentPoint) != null) {
				for (String child : parent2Successors.get(currentPoint)) {
					id2Indegree.put(child, id2Indegree.get(child) - 1);
					if (id2Indegree.get(child) == 0) {
						zeroIndegreePoint.add(child);
					}
				}
			}
		}
		return sortedList;
	}

	/**
	 * calculate indegree for each node
	 * @param parent2Successors
	 * @return
	 */
	public static Map<String, Integer> calculateIndegree(
			Map<String, Collection<String>> parent2Successors) {
		if (parent2Successors == null) {
			return null;
		}
		Map<String, Integer> id2Indegree = new HashMap<String, Integer>();
		int indegree;
		for (Map.Entry<String, Collection<String>> entry : parent2Successors
				.entrySet()) {
			if (!id2Indegree.containsKey(entry.getKey())) {
				id2Indegree.put(entry.getKey(), 0);
			}
			for (String child : entry.getValue()) {
				if (!id2Indegree.containsKey(child)) {
					id2Indegree.put(child, 0);
				}
				indegree = id2Indegree.get(child);
				id2Indegree.put(child, indegree + 1);
			}
		}
		return id2Indegree;
	}

}
